package top.humbleyuan.niuke;

import org.junit.Test;
import top.humbleyuan.leet.Array;
import top.humbleyuan.sortmethod.Heap;


import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.*;

/**
 * @Author HumbleYuan
 * @Date 2020/1/8 15:13
 * @Des 牛客网算法题
 */
public class Algo {

    /**
     * 逆时针遍历数组
     */
    @Test
    public void yuanfudao_1() {
        int row = 3;
        int col = 4;
        //int[][] nums = {{1,4,5,7}, {2,7,3,18}, {5,6,2,9}, {6,4,21,3}};
        int[][] nums = {{2,42,3}, {3,7,8}, {90,67,4}};



        int rMin = 0, cMin = 0;
        int rMax = nums.length - 1;
        int cMax = nums.length - 1;

        while(rMin <= rMax && cMin <= cMax) {
            for(int i = rMin;i <= rMax;i++) {
                System.out.print(nums[i][cMin]+" ");
            }

            for(int j = cMin + 1;j <= cMax;j++) {
                System.out.print(nums[rMax][j]+" ");
            }

            for(int i = rMax - 1;i >= rMin; i--) {
                System.out.print(nums[i][cMax]+" ");
            }

            for(int j = cMax - 1;j > cMin;j--) {
                System.out.print(nums[rMin][j] + " ");
            }
            rMin ++;
            rMax --;
            cMin ++;
            cMax --;
        }

    }

    /**
     *给定两个字符串, A 和 B。A 的旋转操作就是将 A 最左边的字符移动到最右边。
     * 例如, 若 A ='abcde'，在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后，A 能变成B，那么返回True。
     */
    @Test
    public void disifanshi_1() {
        String a,b;

        Scanner aStr = new Scanner(System.in);
        System.out.println("输入A:");
        a = aStr.next();
        System.out.println(a);

        Scanner bStr = new Scanner(System.in);
        System.out.println("输入B:");
        b = bStr.nextLine();


        if(a == null && b == null) {
            System.out.println("true");
            return;
        } else if(a == null || b == null) {
            System.out.println("false");
            return;
        }

        if(a.length() != b.length()) {
            System.out.println("false");
            return;
        }

        int i = 1;
        while (i++ <= a.length()) {
            if(a.equals(b)) {
                System.out.println("true");
                return;
            }
            a = a.substring(1) + a.charAt(0);
        }
        System.out.println("false");

    }

    /**
     * 小易是班级的英语课代表, 他开发了一款软件开处理他的工作。
     * 小易的软件有一个神奇的功能，能够通过一个百分数来反应你的成绩在班上的位置。“成绩超过班级 ...% 的同学”。
     * 设这个百分数为 p，考了 s 分，则可以通过以下式子计算得出 p：
     * p = ( 分数不超过 s 的人数 - 1)  班级总人数
     * 突然一天的英语考试之后，软件突然罢工了，这可忙坏了小易。成绩输入这些对于字写得又快又好的小易当然没有问题，但是计算这些百分数……这庞大的数据量吓坏了他。
     * 于是他来找到你，希望他编一个程序模拟这个软件：给出班级人数 n，以及每个人的成绩，请求出某几位同学的百分数。
     */
    public static void wangyi_1() {
        Scanner scanner = new Scanner(System.in);
        // 有多少同学
        int n = scanner.nextInt();
        System.out.println("有" + n);

        // 跳到下一行
        scanner.nextLine();

        // 所有人分数
        String scores = scanner.nextLine();
        String[] scoreArr = scores.trim().split(" ");
        int[] scoreA = new int[scoreArr.length];
        for (int i = 0; i < scoreArr.length; i++) {
            scoreA[i] = Integer.parseInt(scoreArr[i]);
        }
        System.out.println("分数为" + scores);

        int q = scanner.nextInt();
        System.out.println("询问人数：" + q);

        // 询问人数
        int[] asks = new int[q];

        // 具体询问人
        for (int i = 0; i < q; i++) {
            asks[i] = scanner.nextInt();
        }

        System.out.println(n + "\t" + scores + "\t" + q + "\t" + Arrays.toString(asks));

        // 具体操作
        double[] per = new double[q];
        int[] preScoreA = Arrays.copyOf(scoreA,scoreA.length);
        Arrays.sort(scoreA);

        System.out.println("pre:" + Arrays.toString(preScoreA));

        for (int i = 0; i < q; i++) {
            int s = preScoreA[asks[i] - 1];
            int j;
            for (j = 0; j < scoreA.length; j++) {
                if(scoreA[j] > s) {
                    break;
                }
            }


            BigDecimal bd = new BigDecimal(((double) --j / (double) scoreA.length)*100d).
                    setScale(6, BigDecimal.ROUND_HALF_UP);
            per[i] = bd.doubleValue();

        }

        System.out.println(Arrays.toString(per));

    }

    /**
     * 气球游戏(双指针，滑动窗口)
     * 输入：
     * 12 5
     * 2 5 3 1 3 2 4 1 0 5 4 3
     */
    @Test
    public void tenxu_01() {
        int shootNum = 13;
        int targetNum = 4;
        int[] shootRes = {2,1,3,1,3,2,0,4,1,0,0,4,3};
        int[] color = new int[targetNum + 1];
        int res = -1;

        if(targetNum > shootRes.length) {
            System.out.println(res);
        }

        int pre = 0, back = 0;  // 快慢指针（快指针也应该从0开始）
        int curColorNum = 0;  // 目前射中的颜色总数
        while (back < shootRes.length) {
            // 如果当前射中的颜色在前面都没出现过
            if(shootRes[back] != 0 && color[shootRes[back]] == 0) {
                curColorNum ++;
            }
            color[shootRes[back]] ++;   // 射中的气球颜色+1

            // 满足击中所有颜色气球
            if(targetNum == curColorNum) {

                // 开始移动前指针
                /**
                 * 条件：
                 * 区间 >= 颜色总数 && 移除前一个无影响（前指针指向的是0 || 前指正指向的数字出现次数>1）
                 */
                while ((back - pre) >= (targetNum - 1) &&
                        (shootRes[pre] == 0 || color[shootRes[pre]] > 1)) {
                    color[shootRes[pre]]--; // 当前颜色数量减少
                    pre ++;     // 前指针后移
                }
                if(res == -1 || res > (back - pre + 1)) {
                    res = back - pre + 1;
                }
            }
            back ++;
        }

        System.out.println("最小区间：" + res);



    }

    /**
     * 华为机试：
     * 有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。
     * 以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如
     * 此循环直到最后一个数被删除。
     */
    @Test
    public void huawei_01() {
        Integer[] array = {0,1,2,3,4,5,6};

        List<Integer> list = new ArrayList<>(Arrays.asList(array));
        int curIndex = -1;

        while(list.size() > 1) {

            // 若index超范围重回头
            curIndex = (curIndex + 2) % list.size();

            list.remove(curIndex);
        }

        System.out.println(list.get(0));
    }




}




